package random_test;

public class Test_10_27 {

    //面试题 01.01. 判定字符是否唯一
    public boolean isUnique(String astr) {
        // 当len > 26，必有一个字母重复
        if(astr.length() > 26) return false;

        // 用第 1 ~ 26个比特位代表字母是否出现，其中对应比特位为 1 表示出现， 0 表示未出现
        int flag = 0;
        for(char ch : astr.toCharArray()) {
            int num = ch - 'a';
            // 字母未出现，将flag对应的比特位改为1
            if(((flag>>num) & 1) == 0) {
                flag |= 1<<num;
            } else {
                return false;
            }
        }
        return true;
    }


    //268. 丢失的数字
    public int missingNumber(int[] nums) {
        // 位运算
        int ret = 0;
        for(int i = 0; i < nums.length; i++)
            ret = ret ^ (i + 1) ^ nums[i];
        return ret;
    }


    //260. 只出现一次的数字 III
    public int[] singleNumber(int[] nums) {
        int[] ret = new int[2];
        int product = 0;
        for(int x : nums) product ^= x;
        // 取得product比特中最右边的1
        int k = product & (-product);
        //
        int num1 = 0;
        for(int x : nums) {
            if((x & k) > 0) num1 ^= x;
            System.out.print(num1 + " ");
        }
        ret[0] = num1;
        ret[1] = product ^ num1;
        return ret;
    }


    //137. 只出现一次的数字 II
    public int singleNumber1(int[] nums) {
        int ret = 0;
        for(int i = 0; i < 32; i++) {
            int sum = 0;
            for(int j = 0; j < nums.length; j++) {
                sum += (nums[j]>>i) & 1;
            }
            if(sum % 3 == 1) {
                ret |= 1<<i;
            }
        }
        return ret;
    }


    //面试题 17.19. 消失的两个数字
    public int[] missingTwo(int[] nums) {
        int tmp = 0;
        for(int x : nums) tmp ^= x;
        for(int i = 1; i <= nums.length + 2; i++) tmp ^= i;

        // 此时tmp为待返回的两个数异或的结果
        int flag = tmp & (-tmp);
        int ret = 0;
        for(int x : nums) if((flag & x) > 0) ret ^= x;
        for(int i = 1; i <= nums.length + 2; i++) if((flag & i) > 0) ret ^= i;
        return new int[]{ret, tmp ^ ret};
    }


    //371. 两整数之和
    public int getSum(int a, int b) {
        while(b != 0) {
            int carry = (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
}
